//单点修改+区间查询（不需要懒标记）求区间最大字段和
const int N = 500001;
int w[N];
struct Node{
    int l,r;
    int sum,lmax,rmax,tmax;
}tr[N*4];
int arr[N];
void push_up(Node& u,Node& l,Node& r)
{
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax,l.sum+r.lmax);
    u.rmax = max(r.rmax,r.sum+l.rmax);
    u.tmax = max(max(l.tmax,r.tmax),l.rmax+r.lmax);
}
void push_up(int u)
{
    push_up(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
    if(l==r) tr[u] = {l,r,arr[r],arr[r],arr[r],arr[r]};
    else
    {
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        push_up(u);
    }
}
void modify(int u,int x,int v)
{
    if(tr[u].l==x&&x==tr[u].r) tr[u] = {x,x,v,v,v,v};
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1|1,x,v);
        push_up(u);
    } 
}
Node quary(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
    
    else 
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(r<=mid) return quary(u<<1,l,r);
        else if(l>mid) return quary(u<<1|1,l,r);
        else 
        {
            auto left = quary(u<<1,l,r);
            auto right = quary(u<<1|1,l,r);
            Node res;
            push_up(res,left,right);
            return res;
        }
    }
}
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i<=n;i++) scanf("%d", &arr[i]);
    build(1,1,n);
    while(m--)
    {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1)
        {
            if(x>y) swap(x,y);
            int u = quary(1,x,y).tmax;
            printf("%d\n",u);
        }
        else{
            modify(1,x,y);
        }
    }
}